8.5.1 Random Number Generator

Calc’s random number generator uses several methods to ensure that the numbers it produces are highly random. Knuth’s Art of Computer Programming, Volume II, contains a thorough description of the theory of random number generators and their measurement and characterization.

If RandSeed has no stored value, Calc calls Emacs’s built-in random function to get a stream of random numbers, which it then treats in various ways to avoid problems inherent in the simple random number generators that many systems use to implement random.

When Calc’s random number generator is first invoked, it “seeds” the low-level random sequence using the time of day, so that the random number sequence will be different every time you use Calc.

Since Emacs Lisp doesn’t specify the range of values that will be returned by its random function, Calc exercises the function several times to estimate the range. When Calc subsequently uses the random function, it takes only 10 bits of the result near the most-significant end. (It avoids at least the bottom four bits, preferably more, and also tries to avoid the top two bits.) This strategy works well with the linear congruential generators that are typically used to implement random.

If RandSeed contains an integer, Calc uses this integer to seed an “additive congruential” method (Knuth’s algorithm 3.2.2A, computing ‘X_n-55 - X_n-24’). This method expands the seed value into a large table which is maintained internally; the variable RandSeed is changed from, e.g., 42 to the vector ‘[42]’ to indicate that the seed has been absorbed into this table. When RandSeed contains a vector, k r and related commands continue to use the same internal table as last time. There is no way to extract the complete state of the random number generator so that you can restart it from any point; you can only restart it from the same initial seed value. A simple way to restart from the same seed is to type s r RandSeed to get the seed vector, v u to unpack it back into a number, then s t RandSeed to reseed the generator with that number.

Calc uses a “shuffling” method as described in algorithm 3.2.2B of Knuth. It fills a table with 13 random 10-bit numbers. Then, to generate a new random number, it uses the previous number to index into the table, picks the value it finds there as the new random number, then replaces that table entry with a new value obtained from a call to the base random number generator (either the additive congruential generator or the random function supplied by the system). If there are any flaws in the base generator, shuffling will tend to even them out. But if the system provides an excellent random function, shuffling will not damage its randomness.

To create a random integer of a certain number of digits, Calc builds the integer three decimal digits at a time. For each group of three digits, Calc calls its 10-bit shuffling random number generator (which returns a value from 0 to 1023); if the random value is 1000 or more, Calc throws it out and tries again until it gets a suitable value.

To create a random floating-point number with precision p, Calc simply creates a random p-digit integer and multiplies by ‘10^-p’. The resulting random numbers should be very clean, but note that relatively small numbers will have few significant random digits. In other words, with a precision of 12, you will occasionally get numbers on the order of ‘10^-9’ or ‘10^-10’, but those numbers will only have two or three random digits since they correspond to small integers times ‘10^-12’.

To create a random integer in the interval ‘[0 .. m)’, Calc counts the digits in m, creates a random integer with three additional digits, then reduces modulo m. Unless m is a power of ten the resulting values will be very slightly biased toward the lower numbers, but this bias will be less than 0.1%. (For example, if m is 42, Calc will reduce a random integer less than 100000 modulo 42 to get a result less than 42. It is easy to show that the numbers 40 and 41 will be only 2380/2381 as likely to result from this modulo operation as numbers 39 and below.) If m is a power of ten, however, the numbers should be completely unbiased.

The Gaussian random numbers generated by ‘random(0.0)’ use the “polar” method described in Knuth section 3.4.1C. This method generates a pair of Gaussian random numbers at a time, so only every other call to ‘random(0.0)’ will require significant calculations.